def find_frequent_1_itemsets(D):
    # 找出频繁1项集的集合L1
    L1 = []
    for i in D:
        for j in i:
            if [j] not in L1:
                L1.append([j])
    L1.sort()
    return L1


def apriori_gen(L_k_1, k):
    # 产生第k次的候选集
    # L_k_1 为 list[ [] ]
    # print('---k', k)
    # print('--L_k_1', L_k_1)

    # 储存候选集
    C_k = []
    # 储存子集，用于剪枝
    c = []
    for i in range(len(L_k_1)):
        for j in range(i + 1, len(L_k_1)):
            l1 = list(L_k_1[i])[:k - 2]
            l2 = list(L_k_1[j])[:k - 2]
            # print('--l1', l1)
            # print('--l2', l2)
            if l1 == l2:
                new = list(set(L_k_1[i]) ^ set(L_k_1[j]))
                new.sort()
                ne = l1 + new
                # new = tuple(new)
                # print('---new', new)
                C_k.append(ne)
                # print('--l1', l1)
                for x in range(len(l1)-2):
                    for y in range(i+1, len(l1)-1):
                        a = [l1[x]]
                        b = [l1[y]]
                        n = a+b+new
                        # print('---n', n)
                        c.append(n)
                        # print('--c', c)
    # print('---C--i', C_k)
    # 产生2次以上的候选集时进行剪枝
    if k > 2:
        for a in range(len(c)):
            # print('---a', a)
            if c[a] not in L_k_1:
                # print('--c[a]', c[a])
                # print('---C-i', C_k[a])
                del C_k[a]
    # print('---C_', k, C_k)
    return C_k


def scan_D_t(D):  # minSupport为设定的最小支持度
    # 扫描D产生所有子集和其支持度
    # D [['a', 'b', 'c'], ['d', 'f']]
    output = {}
    res = []
    for num in D:
        n = len(num)

        def helper(i, tmp):
            if tmp:
                tmp.sort()
                s = ''.join(tmp)
                res.append(tmp)
                if s not in output:
                    output[s] = 1
                else:
                    output[s] = output[s] + 1
            for j in range(i, n):
                helper(j + 1, tmp + [num[j]])

        helper(0, [])
    res.append(find_frequent_1_itemsets(D))
    return res, output


def scan_D(Ck, Di, minSupport):
    # 候选集与数据集中进行最小支持度比较
    Ck_i = []
    for i in Ck:
        for j in Di:
            s = ''.join(('%s' %id for id in j))
            if s == j and Di[j] >= minSupport:
                Ck_i.append(i)
    return Ck_i

#
# f = open('D:\\hanxiii\\study\\数据挖掘\\关联规则\\dataset.txt', encoding='gbk')
# data = []
# for line in f.readlines()[1:]:
#     line = list(line.strip().split('	'))
#     data.append(line)
# print(data)
# d = []
# for i in data:
#     s = i[1]
#     s = list(s.strip().split(', '))
#     d.append(s)
# print(d)
# A = find_frequent_1_itemsets(d)  # 生成第一个候选集
# print('--A', A)
# B, C = scan_D_t(d)  # B为所有子集  C为数据集所有子集的计数
# print('--B', B)
# print('--C', C)
# D = scan_D(A, C, 2)  # D为A中满足最小支持度的项集
# print('--D', D)
# E = D
# k = 1
# while D:
#     E = D
#     # print('--D', k, E)
#     k = k+1
#     A = apriori_gen(D, k)
#     # print('---A', k, A)
#     D = scan_D(A, C, 2)
#     # print('--D', k, D)
#
# print('-----final---', E)
